Virtually all complex integrated circuits are designed with the use of computer aided design (CAD) tools. Some CAD tools, called simulators, help the circuit designer verify the operation of a proposed circuit. Another type of CAD tool, called a silicon compiler (also sometimes known as automatic layout or place and route systems), generates the semiconductor mask patterns from a detailed circuit specification. These semiconductor mask patterns for a particular circuit are commonly called the "circuit layout".
Circuit layouts have multiple overlapping mask layers for defining different mask levels (also called layout levels) of a semiconductor integrated circuit. For instance, some layers of the circuit layout will define the regions of the semiconductor substrate that are doped with N-type or P-type dopants, while other layers of the circuit layout will define regions in which materials are deposited on the top of the substrate, such as polysilicon and metal regions, while yet other layers will define apertures to be formed in various layers of material so as to form connections between layers of the semiconductor circuit.
Each layer of a circuit layout is defined as a set of polygons or cells. In some systems, the cells must be rectangles, but most circuit layout systems allow the use of trapezoids and/or polygons whose sides are all vertical, horizontal or at a 45-degree angle to such vertical and horizontal sides.
Typically, a circuit layout will be prepared for a particular set of design rules. For instance, one will often hear that a circuit was manufactured using "2 micron design rules" or "2 micron minimum critical dimensions". Such phrases mean that certain features of the circuit's layout have minimum widths of 2 microns. Later, a faster version of that same circuit may be manufactured using "1 micron design rules" or "1 micron minimum critical dimensions".
While a number of attempts have been made in the past to compress or compact circuit layouts using automated computer techniques, most such prior automatic circuit layout compression systems use graph theory or linear programming methods, and thus lose at least some of the useful information and optimizations in the original layout. In addition, many of the prior art techniques are unable to handle layouts that include polygons with sides at 45 degree angles, and most require so many computer operations as to be impractical commercially.
One method for compacting integrated circuit layouts is known as the constraint graph method, which involves generating a layout data. structure for an input layout, and then generating an additional, graphically based data structure. The layout is minimized using a "longest paths" algorithm, which involves finding the longest path through "edges" (or paths) through "nodes" of the layout, where the node indicate locations of cells. These longest paths are reduced by modifying positions of the cells, to make the layout smaller.
The constraint graph method does not present an efficient means for sizing transistors, which are subject to different design rules than other cells in a layout. In addition, it requires the use of the additional, graphical data structure, which presents a N.sup.2 problem to the processor, N being the number of cells in the layout. Other .current layout compaction procedures are not efficient at handling compaction of layouts, and in particular at resizing transistors as desired during such compaction.
One method for designing integrated circuits is known as the "standard cell" method. Standard cells are relatively small circuit elements, formed in silicon, that are part of a digital design. Examples of standard cells include NAND gates, flip-flops, and multiplexers. They are called standard cells because each cell has a standard height.
Standard cells must meet specific design requirements, or architecture rules, so that an automatic place and route program can automatically place copies of these cells and automatically generate the layout wiring that connects the cells together to create a complete digital integrated circuit design. Compaction of standard cells is hindered by the fact that the compaction operation cannot violate these standard cell architecture rules. One standard cell architecture rule is that power and ground metal must be of a minimum specified width. Another standard cell architecture rule is that power and ground metal-1 must be placed at a specified y-grid location on the left and right ends of the cell. This placement insures alignment with another cell's power and ground metal-1. Another standard cell rule is that all metal-2 interconnect within the cell must be placed so as to maximize areas where metal-2 can be routed through the cell.
A number of standard cell rules apply to I/O ports. For example, an external I/O port is required to be located at the perimeter of the cell and must be on a specified routing grid used by the place and route tool. An internal I/O port is located inside the cell and must be on the specified routing grid.
It would be highly desirable to provide an apparatus and method to automatically compact standard cell architectures in such a manner that standard cell design rules are not violated.